package com.gitee.wsl.collections.map

import com.gitee.wsl.base.Objects.equals
import com.gitee.wsl.collections.bean.HashEntry
import com.gitee.wsl.collections.iterator.EmptyMutableIterator
import com.gitee.wsl.collections.iterator.api.MapIterator
import com.gitee.wsl.collections.iterator.api.MutableMapEntry
import com.gitee.wsl.collections.iterator.api.MutableMapIterator
import com.gitee.wsl.ext.base.COMMA
import kotlin.jvm.Transient
import kotlin.math.max

/**
 * An abstract implementation of a hash-based map which provides numerous points for
 * subclasses to override.
 *
 *
 * This class implements all the features necessary for a subclass hash-based map.
 * Key-value entries are stored in instances of the `HashEntry` class,
 * which can be overridden and replaced. The iterators can similarly be replaced,
 * without the need to replace the KeySet, EntrySet and Values view classes.
 *
 *
 *
 * Overridable methods are provided to change the default hashing behavior, and
 * to change how entries are added to and removed from the map. Hopefully, all you
 * need for unusual subclasses is here.
 *
 *
 *
 * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
 * This extends clause will be removed in v5.0.
 *
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0
</V></K> */
open class AbstractHashedMap<K, V> : AbstractMutableMap<K, V> {
    /**
     * EntrySet implementation.
     *
     * @param <K> the type of the keys in the map
     * @param <V> the type of the values in the map
    </V></K> */
    class EntrySet<K, V>(
        /** The parent map  */
        private val parent: AbstractHashedMap<K,V>,
    ) : AbstractMutableSet<MutableMapEntry<K, V>>() {
         override fun clear() {
            parent.clear()
        }

         override fun contains(element: MutableMapEntry<K, V>): Boolean {
           val match = parent.getEntry(element.key)
           return match != null && match.equals(element)
        }

         override fun iterator(): MutableIterator<MutableMapEntry<K, V>> {
            return parent.createEntrySetIterator()
        }

        override fun add(element: MutableMapEntry<K, V>): Boolean {
            TODO("Not yet implemented")
        }

         override fun remove(element: MutableMapEntry<K, V>): Boolean {
            if (!contains(element)) {
                return false
            }
            val entry = element as Map.Entry<*, *>
            parent.remove(entry.key)
            return true
        }

        override val size: Int
            get() = parent.size
    }

    /**
     * EntrySet iterator.
     *
     * @param <K> the type of the keys in the map
     * @param <V> the type of the values in the map
    </V></K> */
    protected class EntrySetIterator<K, V> (
        parent: AbstractHashedMap<K,V>
    ) : HashIterator<K,V>(parent), MutableIterator<MutableMapEntry<K,V>> {
         override fun next(): MutableMapEntry<K, V> {
            return super.nextEntry()
        }
    }


    /**
     * Base Iterator.
     *
     * @param <K> the type of the keys in the map
     * @param <V> the type of the values in the map
    </V></K> */
    protected abstract class HashIterator<K, V> protected constructor(
        /** The parent map  */
        private val parent: AbstractHashedMap<K, V>
    ) {

        /** The current index into the array of buckets  */
        private var hashIndex: Int

        /** The last returned entry  */
        private var last: HashEntry<K, V>? = null

        /** The next entry  */
        private var next: HashEntry<K,V>?

        /** The modification count expected  */
        private var expectedModCount: Int

        /**
         * Constructs a new instance.
         *
         * @param parent The parent AbstractHashedMap.
         */
        init {
            val data = parent.data
            var i = data.size
            var next: HashEntry<K,V>? = null
            while (i > 0 && next == null) {
                next = data[--i]
            }
            this.next = next
            this.hashIndex = i
            this.expectedModCount = parent.modCount
        }

        /**
         * Gets the current entry.
         *
         * @return the current entry.
         */
        protected fun currentEntry(): HashEntry<K,V> {
            return last!!
        }

        /**
         * Tests whether there is a next entry.
         *
         * @return whether there is a next entry.
         */
        fun hasNext(): Boolean {
            return next != null
        }


        /**
         * Gets the next entry.
         *
         * @return the next entry.
         */
        protected fun nextEntry(): HashEntry<K,V> {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
            val newCurrent = next
            if (newCurrent == null) {
                throw NoSuchElementException(NO_NEXT_ENTRY)
            }
            val data = parent.data
            var i = hashIndex
            var n = newCurrent.next
            while (n == null && i > 0) {
                n = data[--i]
            }
            next = n
            hashIndex = i
            last = newCurrent
            return newCurrent
        }

        /**
         * Removes the current element.
         */
        fun remove() {
            checkNotNull(last) { REMOVE_INVALID }
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
            parent.remove(last!!.key!!)
            last = null
            expectedModCount = parent.modCount
        }

        override fun toString(): String {
            if (last != null) {
                return "Iterator[" + last!!.key + "=" + last!!.value + "]"
            }
            return "Iterator[]"
        }
    }

    /**
     * MapIterator implementation.
     *
     * @param <K> the type of the keys in the map
     * @param <V> the type of the values in the map
    </V></K> */
    protected class HashMapIterator<K, V>(
        parent: AbstractHashedMap<K,V>
    ) : HashIterator<K,V>(parent), MutableMapIterator<K, V> {
        override fun getKey(): K {
            val current = currentEntry()
            checkNotNull(current) { GETKEY_INVALID }
            return current.key
        }

        override fun getValue(): V {
            val current = currentEntry()
            checkNotNull(current) { GETVALUE_INVALID }
            return current.value
        }

        override fun next(): K {
            return super.nextEntry().key
        }

        override fun setValue(value: V): V {
            val current = currentEntry()
            checkNotNull(current) { SETVALUE_INVALID }
            return current.setValue(value)
        }
    }

    /**
     * KeySet implementation.
     *
     * @param <K> the type of elements maintained by this set
    </K> */
    class KeySet<K,V>(
        /** The parent map  */
        private val parent: AbstractHashedMap<K, V>,
    ) : AbstractMutableSet<K>() {
         override fun clear() {
            parent.clear()
        }

         override fun contains(element: K): Boolean {
            return parent.containsKey(element)
        }

         override fun iterator(): MutableIterator<K> {
            return parent.createKeySetIterator()
        }

        override fun add(element: K): Boolean {
            TODO("Not yet implemented")
        }

        override fun remove(element: K): Boolean {
            val result = parent.containsKey(element)
            parent.remove(element)
            return result
        }

        override val size: Int
            get() = parent.size

    }

    /**
     * KeySet iterator.
     *
     * @param <K> the type of elements maintained by this set
    </K> */
    protected class KeySetIterator<K,V> (
        parent: AbstractHashedMap<K, V>
    ) : HashIterator<K, V>(parent), MutableIterator<K>{
        override fun next(): K {
            return super.nextEntry().key
        }
    }

    /**
     * Values implementation.
     *
     * @param <V> the type of elements maintained by this collection
    </V> */
    class Values<K,V>(
        /** The parent map  */
        private val parent: AbstractHashedMap<K, V>,
    ) : AbstractMutableCollection<V>() {
         override fun clear() {
            parent.clear()
        }

         override fun contains(element: V): Boolean {
            return parent.containsValue(element)
        }

         override fun iterator(): MutableIterator<V> {
            return parent.createValuesIterator()
        }

        override fun add(element: V): Boolean {
            TODO("Not yet implemented")
        }

        override val size: Int
            get() =  parent.size

    }

    /**
     * Values iterator.
     *
     * @param <V> the type of elements maintained by this collection
    </V> */
    protected class ValuesIterator<K,V>(
        parent: AbstractHashedMap<K, V>
    ) : HashIterator<K, V>(parent), MutableIterator<V>{
        override fun next(): V {
            return super.nextEntry().value
        }
    }

    /** Load factor, normally 0.75  */
    @Transient
    var loadFactor: Float = 0f

    /** The size of the map  */
    @Transient
    override var size: Int = 0

    /** Map entries  */
    @Transient
    lateinit var data: Array<HashEntry<K,V>?>

    /** Size at which to rehash  */
    @Transient
    var threshold: Int = 0

    /** Modification count for iterators  */
    @Transient
    var modCount: Int = 0

    /** Entry set  */
    @Transient
    protected var entrySet: EntrySet<K,V>? = null

    /** Key set  */
    @Transient
    protected var keySet: KeySet<K,V>? = null

    /** Values  */
    @Transient
    protected var _values: MutableCollection<V>?=null

    /** Values  */
    override val values: MutableCollection<V>
        get() {
             if (_values == null) {
                 _values = Values(this)
               }
           return _values!!
        }

    override val entries: MutableSet<MutableMap.MutableEntry<K, V>>
        get() {
           if (entrySet == null) {
               entrySet = EntrySet(this)
            }
           return entrySet!!
        }

    override val keys: MutableSet<K>
        get(){
            if (keySet == null) {
                keySet = KeySet(this )
            }
            return keySet!!
        }

    /**
     * Constructor only used in deserialization, do not use otherwise.
     */
    protected constructor()

    /**
     * Constructs a new, empty map with the specified initial capacity and
     * load factor.
     *
     * @param initialCapacity  the initial capacity
     * @param loadFactor  the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     * @throws IllegalArgumentException if the load factor is less than or equal to zero
     */
    /**
     * Constructs a new, empty map with the specified initial capacity and
     * default load factor.
     *
     * @param initialCapacity  the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    protected constructor(initialCapacity: Int, loadFactor: Float = DEFAULT_LOAD_FACTOR) {
        var initialCapacity = initialCapacity
        require(initialCapacity >= 0) { "Initial capacity must be a non negative number" }
        require(!(loadFactor <= 0.0f || loadFactor.isNaN())) { "Load factor must be greater than 0" }
        this.loadFactor = loadFactor
        initialCapacity = calculateNewCapacity(initialCapacity)
        this.threshold = calculateThreshold(initialCapacity, loadFactor)
        this.data = arrayOfNulls<HashEntry<K,V>>(initialCapacity)
        init()
    }

    /**
     * Constructor which performs no validation on the passed in parameters.
     *
     * @param initialCapacity  the initial capacity, must be a power of two
     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
     * @param threshold  the threshold, must be sensible
     */
    protected constructor(initialCapacity: Int, loadFactor: Float, threshold: Int) {
        this.loadFactor = loadFactor
        this.data = kotlin.arrayOfNulls<HashEntry<K,V>>(initialCapacity)
        this.threshold = threshold
        init()
    }

    /**
     * Constructor copying elements from another map.
     *
     * @param map  the map to copy
     * @throws NullPointerException if the map is null
     */
    protected constructor(map: Map< K,  V>) : this(
        max(2 * map.size, DEFAULT_CAPACITY),
        DEFAULT_LOAD_FACTOR
    ) {
        putAll(map)
    }

    /**
     * Adds an entry into this map.
     *
     *
     * This implementation adds the entry to the data storage table.
     * Subclasses could override to handle changes to the map.
     *
     *
     * @param entry  the entry to add
     * @param hashIndex  the index into the data array to store at
     */
    protected open fun addEntry(entry: HashEntry<K,V>, hashIndex: Int) {
        data[hashIndex] = entry
    }

    /**
     * Adds a new key-value mapping into this map.
     *
     *
     * This implementation calls `createEntry()`, `addEntry()`
     * and `checkCapacity()`.
     * It also handles changes to `modCount` and `size`.
     * Subclasses could override to fully control adds to the map.
     *
     *
     * @param hashIndex  the index into the data array to store at
     * @param hashCode  the hash code of the key to add
     * @param key  the key to add
     * @param value  the value to add
     */
    fun addMapping(hashIndex: Int, hashCode: Int, key: K, value: V) {
        modCount++
        val entry = createEntry(data[hashIndex], hashCode, key, value)
        addEntry(entry, hashIndex)
        size++
        checkCapacity()
    }

    /**
     * Calculates the new capacity of the map.
     * This implementation normalizes the capacity to a power of two.
     *
     * @param proposedCapacity  the proposed capacity
     * @return the normalized new capacity
     */
    protected fun calculateNewCapacity(proposedCapacity: Int): Int {
        var newCapacity = 1
        if (proposedCapacity > MAXIMUM_CAPACITY) {
            newCapacity = MAXIMUM_CAPACITY
        } else {
            while (newCapacity < proposedCapacity) {
                newCapacity = newCapacity shl 1 // multiply by two
            }
            if (newCapacity > MAXIMUM_CAPACITY) {
                newCapacity = MAXIMUM_CAPACITY
            }
        }
        return newCapacity
    }

    /**
     * Calculates the new threshold of the map, where it will be resized.
     * This implementation uses the load factor.
     *
     * @param newCapacity  the new capacity
     * @param factor  the load factor
     * @return the new resize threshold
     */
    protected fun calculateThreshold(newCapacity: Int, factor: Float): Int {
        return (newCapacity * factor).toInt()
    }

    /**
     * Checks the capacity of the map and enlarges it if necessary.
     *
     *
     * This implementation uses the threshold to check if the map needs enlarging
     *
     */
    protected fun checkCapacity() {
        if (size >= threshold) {
            val newCapacity = data.size * 2
            if (newCapacity <= MAXIMUM_CAPACITY) {
                ensureCapacity(newCapacity)
            }
        }
    }

    /**
     * Clears the map, resetting the size to zero and nullifying references
     * to avoid garbage collection issues.
     */
     override fun clear() {
        modCount++
        val data = this.data
        data.fill(null)
        size = 0
    }

    /**
     * Clones the map without cloning the keys or values.
     *
     *
     * To implement `clone()`, a subclass must implement the
     * `Cloneable` interface and make this method .
     *
     *
     * @return a shallow clone
     * @throws InternalError if [AbstractMap.clone] failed
     */
//    override fun clone(): AbstractHashedMap<K,V> {
//        try {
//            val cloned = super.clone() as AbstractHashedMap<K,V>
//            cloned.data = kotlin.arrayOfNulls<HashEntry<*, *>>(data.size)
//            cloned.entrySet = null
//            cloned.keySet = null
//            cloned.values = null
//            cloned.modCount = 0
//            cloned.size = 0
//            cloned.init()
//            cloned.putAll(this)
//            return cloned
//        } catch (ex: java.lang.CloneNotSupportedException) {
//            throw java.lang.UnsupportedOperationException(ex)
//        }
//    }

    /**
     * Checks whether the map contains the specified key.
     *
     * @param key  the key to search for
     * @return true if the map contains the key
     */
     override fun containsKey(key: K): Boolean {
        var key = key
        key = convertKey(key)
        val hashCode = hash(key)
        var entry = data[hashIndex(hashCode, data.size)] // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return true
            }
            entry = entry.next
        }
        return false
    }

    /**
     * Checks whether the map contains the specified value.
     *
     * @param value  the value to search for
     * @return true if the map contains the value
     */
     override fun containsValue(value: V): Boolean {
        if (value == null) {
            for (element in data) {
                var entry = element
                while (entry != null) {
                    if (entry.value == null) {
                        return true
                    }
                    entry = entry.next
                }
            }
        } else {
            for (element in data) {
                var entry = element
                while (entry != null) {
                    if (isEqualValue(value, entry.value)) {
                        return true
                    }
                    entry = entry.next
                }
            }
        }
        return false
    }

    /**
     * Converts input keys to another object for storage in the map.
     * This implementation masks nulls.
     * Subclasses can override this to perform alternate key conversions.
     *
     *
     * The reverse conversion can be changed, if required, by overriding the
     * getKey() method in the hash entry.
     *
     *
     * @param key  the key convert
     * @return the converted key
     */
    protected fun convertKey(key: K): K {
        return key
    }

    /**
     * Creates an entry to store the key-value data.
     *
     *
     * This implementation creates a new HashEntry instance.
     * Subclasses can override this to return a different storage class,
     * or implement caching.
     *
     *
     * @param next  the next entry in sequence
     * @param hashCode  the hash code to use
     * @param key  the key to store
     * @param value  the value to store
     * @return the newly created entry
     */
    protected open fun createEntry(next: HashEntry<K,V>?, hashCode: Int, key: K, value: V): HashEntry<K,V> {
        return HashEntry( convertKey(key), value, hashCode,next)
    }

    /**
     * Creates an entry set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the entrySet iterator
     */
    protected open fun createEntrySetIterator(): MutableIterator<MutableMapEntry<K,V>> {
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return EntrySetIterator(this)
    }

    /**
     * Creates a key set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the keySet iterator
     */
    protected open fun createKeySetIterator(): MutableIterator<K> {
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return KeySetIterator(this)
    }

    /**
     * Creates a values iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the values iterator
     */
    protected open fun createValuesIterator(): MutableIterator<V>{
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return ValuesIterator(this)
    }

    /**
     * Kills an entry ready for the garbage collector.
     *
     *
     * This implementation prepares the HashEntry for garbage collection.
     * Subclasses can override this to implement caching (override clear as well).
     *
     *
     * @param entry  the entry to destroy
     */
    protected open fun destroyEntry(entry: HashEntry<K,V>) {
        entry.next = null
        //entry.key = null
        //entry.value = null
    }

    /**
     * Reads the map data from the stream. This method must be overridden if a
     * subclass must be setup before `put()` is used.
     *
     *
     * Serialization is not one of the JDK's nicest topics. Normal serialization will
     * initialize the superclass before the subclass. Sometimes however, this isn't
     * what you want, as in this case the `put()` method on read can be
     * affected by subclass state.
     *
     *
     *
     * The solution adopted here is to deserialize the state data of this class in
     * this protected method. This method must be called by the
     * `readObject()` of the first serializable subclass.
     *
     *
     *
     * Subclasses may override if the subclass has a specific field that must be present
     * before `put()` or `calculateThreshold()` will work correctly.
     *
     *
     * @param in  the input stream
     * @throws IOException if an error occurs while reading from the stream
     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
     */
//    @Throws(IOException::class, java.lang.ClassNotFoundException::class)
//    protected fun doReadObject(`in`: ObjectInputStream) {
//        loadFactor = `in`.readFloat()
//        val capacity: Int = `in`.readInt()
//        val size: Int = `in`.readInt()
//        init()
//        threshold = calculateThreshold(capacity, loadFactor)
//        data = kotlin.arrayOfNulls<HashEntry<*, *>>(capacity)
//        for (i in 0..<size) {
//            val key = `in`.readObject() as K?
//            val value = `in`.readObject() as V?
//            put(key, value)
//        }
//    }

    /**
     * Writes the map data to the stream. This method must be overridden if a
     * subclass must be setup before `put()` is used.
     *
     *
     * Serialization is not one of the JDK's nicest topics. Normal serialization will
     * initialize the superclass before the subclass. Sometimes however, this isn't
     * what you want, as in this case the `put()` method on read can be
     * affected by subclass state.
     *
     *
     *
     * The solution adopted here is to serialize the state data of this class in
     * this protected method. This method must be called by the
     * `writeObject()` of the first serializable subclass.
     *
     *
     *
     * Subclasses may override if they have a specific field that must be present
     * on read before this implementation will work. Generally, the read determines
     * what must be serialized here, if anything.
     *
     *
     * @param out  the output stream
     * @throws IOException if an error occurs while writing to the stream
     */
//    @Throws(IOException::class)
//    protected fun doWriteObject(out: ObjectOutputStream) {
//        out.writeFloat(loadFactor)
//        out.writeInt(data.size)
//        out.writeInt(size)
//        val it = mapIterator()
//        while (it.hasNext()) {
//            out.writeObject(it.next())
//            out.writeObject(it.getValue())
//        }
//    }

    /**
     * Changes the size of the data structure to the capacity proposed.
     *
     * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
     */
    protected fun ensureCapacity(newCapacity: Int) {
        val oldCapacity = data.size
        if (newCapacity <= oldCapacity) {
            return
        }
        if (isEmpty()) {
            threshold = calculateThreshold(newCapacity, loadFactor)
            data = arrayOfNulls<HashEntry<K,V>>(newCapacity)
        } else {
            val oldEntries = data
            val newEntries = arrayOfNulls<HashEntry<K,V>>(newCapacity)

            modCount++
            for (i in oldCapacity - 1 downTo 0) {
                var entry = oldEntries[i]
                if (entry != null) {
                    oldEntries[i] = null // gc
                    do {
                        val next = entry!!.next
                        val index = hashIndex(entry.hashCode, newCapacity)
                        entry.next = newEntries[index]
                        newEntries[index] = entry
                        entry = next
                    } while (entry != null)
                }
            }
            threshold = calculateThreshold(newCapacity, loadFactor)
            data = newEntries
        }
    }

    /**
     * Gets the `hashCode` field from a `HashEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `hashCode` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryHashCode(entry: HashEntry<K,V>): Int {
        return entry.hashCode
    }

    /**
     * Gets the `key` field from a `HashEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `key` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryKey(entry: HashEntry<K,V>): K? {
        return entry.key
    }

    /**
     * Gets the `next` field from a `HashEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `next` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryNext(entry: HashEntry<K,V>): HashEntry<K,V>? {
        return entry.next
    }


    /**
     * Gets the `value` field from a `HashEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `value` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryValue(entry: HashEntry<K,V>): V? {
        return entry.value
    }

    /**
     * Compares this map with another.
     *
     * @param other  the object to compare to
     * @return true if equal
     */
    override fun equals(other: Any?): Boolean {
        if (other === this) {
            return true
        }
        if (other !is Map<*, *>) {
            return false
        }
        val map = other as Map<*, *>
        if (map.size !=size) {
            return false
        }
        val it: MapIterator<*, *> = mapIterator()
        try {
            while (it.hasNext()) {
                val key: Any? = it.next()
                val value: Any? = it.getValue()
                if (value == null) {
                    if (map[key] != null || !map.containsKey(key)) {
                        return false
                    }
                } else if (value != map[key]) {
                    return false
                }
            }
        } catch (ignored: ClassCastException) {
            return false
        } catch (ignored: NullPointerException) {
            return false
        }
        return true
    }

    /**
     * Gets the value mapped to the key specified.
     *
     * @param key  the key
     * @return the mapped value, null if no match
     */
     override fun get(key: K): V? {
        var key = key
        key = convertKey(key)
        val hashCode = hash(key)
        var entry = data[hashIndex(hashCode, data.size)] // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return entry.value
            }
            entry = entry.next
        }
        return null
    }

    /**
     * Gets the entry mapped to the key specified.
     *
     *
     * This method exists for subclasses that may need to perform a multi-step
     * process accessing the entry. The  methods in this class don't use this
     * method to gain a small performance boost.
     *
     *
     * @param key  the key
     * @return the entry, null if no match
     */
    protected open fun getEntry(key: K): HashEntry<K,V>? {
        var key = key
        key = convertKey(key)
        val hashCode = hash(key)
        var entry = data[hashIndex(hashCode, data.size)] // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return entry
            }
            entry = entry.next
        }
        return null
    }

    /**
     * Gets the hash code for the key specified.
     * This implementation uses the additional hashing routine from JDK1.4.
     * Subclasses can override this to return alternate hash codes.
     *
     * @param key  the key to get a hash code for
     * @return the hash code
     */
    protected fun hash(key: K): Int {
        // same as JDK 1.4
        var h = key.hashCode()
        h += (h shl 9).inv()
        h = h xor (h ushr 14)
        h += h shl 4
        h = h xor (h ushr 10)
        return h
    }

    /**
     * Gets the standard Map hashCode.
     *
     * @return the hash code defined in the Map interface
     */
    override fun hashCode(): Int {
        var total = 0
        val it = createEntrySetIterator()
        while (it.hasNext()) {
            total += it.next().hashCode()
        }
        return total
    }

    /**
     * Gets the index into the data storage for the hashCode specified.
     * This implementation uses the least significant bits of the hashCode.
     * Subclasses can override this to return alternate bucketing.
     *
     * @param hashCode  the hash code to use
     * @param dataSize  the size of the data to pick a bucket from
     * @return the bucket index
     */
    fun hashIndex(hashCode: Int, dataSize: Int): Int {
        return hashCode and dataSize - 1
    }

    /**
     * Initialize subclasses during construction, cloning or deserialization.
     */
    protected open fun init() {
        // noop
    }

    /**
     * Checks whether the map is currently empty.
     *
     * @return true if the map is currently size zero
     */
     override fun isEmpty(): Boolean {
        return size == 0
    }

    /**
     * Compares two keys, in internal converted form, to see if they are equal.
     * This implementation uses the equals method and assumes neither key is null.
     * Subclasses can override this to match differently.
     *
     * @param key1  the first key to compare passed in from outside
     * @param key2  the second key extracted from the entry via `entry.key`
     * @return true if equal
     */
    protected fun isEqualKey(key1: Any?, key2: Any?): Boolean {
        return equals(key1, key2)
    }

    /**
     * Compares two values, in external form, to see if they are equal.
     * This implementation uses the equals method and assumes neither value is null.
     * Subclasses can override this to match differently.
     *
     * @param value1  the first value to compare passed in from outside
     * @param value2  the second value extracted from the entry via `getValue()`
     * @return true if equal
     */
    protected fun isEqualValue(value1: Any?, value2: Any?): Boolean {
        return equals(value1, value2)
    }
    
    /**
     * Gets an iterator over the map.
     * Changes made to the iterator affect this map.
     *
     *
     * A MapIterator returns the keys in the map. It also provides convenient
     * methods to get the key and value, and set the value.
     * It avoids the need to create an entrySet/keySet/values object.
     * It also avoids creating the Map.Entry object.
     *
     *
     * @return the map iterator
     */
    open fun mapIterator(): MutableMapIterator<K,V> {
//        if (isEmpty()) {
//            return EmptyMapIterator
//        }
        return HashMapIterator(this)
    }

    /**
     * Puts a key-value mapping into this map.
     *
     * @param key  the key to add
     * @param value  the value to add
     * @return the value previously mapped to this key, null if none
     */
     override fun put(key: K, value: V): V? {
        val convertedKey = convertKey(key)
        val hashCode = hash(convertedKey)
        val index = hashIndex(hashCode, data.size)
        var entry = data[index]
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) {
                val oldValue = entry.value
                updateEntry(entry, value)
                return oldValue
            }
            entry = entry.next
        }

        addMapping(index, hashCode, key, value)
        return null
    }

    /**
     * Puts all the values from the specified map into this map.
     *
     *
     * This implementation iterates around the specified map and
     * uses [.put].
     *
     *
     * @param from  the map to add
     * @throws NullPointerException if the map is null
     */
     override fun putAll(from: Map<out K, V>) {
        val mapSize: Int = from.size
        if (mapSize == 0) {
            return
        }
        val newSize = ((size + mapSize) / loadFactor + 1).toInt()
        ensureCapacity(calculateNewCapacity(newSize))
        for (entry in from.entries) {
            put(entry.key, entry.value)
        }
    }

    /**
     * Removes the specified mapping from this map.
     *
     * @param key  the mapping to remove
     * @return the value mapped to the removed key, null if key not in map
     */
     override fun remove(key: K): V? {
        var key = key
        key = convertKey(key)
        val hashCode = hash(key)
        val index = hashIndex(hashCode, data.size)
        var entry = data[index]
        var previous: HashEntry<K,V>? = null
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                val oldValue = entry.value
                removeMapping(entry, index, previous)
                return oldValue
            }
            previous = entry
            entry = entry.next
        }
        return null
    }

    /**
     * Removes an entry from the chain stored in a particular index.
     *
     *
     * This implementation removes the entry from the data storage table.
     * The size is not updated.
     * Subclasses could override to handle changes to the map.
     *
     *
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    protected open fun removeEntry(entry: HashEntry<K,V>, hashIndex: Int, previous: HashEntry<K,V>?) {
        if (previous == null) {
            data[hashIndex] = entry.next
        } else {
            previous.next = entry.next
        }
    }

    /**
     * Removes a mapping from the map.
     *
     *
     * This implementation calls `removeEntry()` and `destroyEntry()`.
     * It also handles changes to `modCount` and `size`.
     * Subclasses could override to fully control removals from the map.
     *
     *
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    fun removeMapping(entry: HashEntry<K,V>, hashIndex: Int, previous: HashEntry<K,V>?) {
        modCount++
        removeEntry(entry, hashIndex, previous)
        size--
        destroyEntry(entry)
    }

    /**
     * Reuses an existing key-value mapping, storing completely new data.
     *
     *
     * This implementation sets all the data fields on the entry.
     * Subclasses could populate additional entry fields.
     *
     *
     * @param entry  the entry to update, not null
     * @param hashIndex  the index in the data array
     * @param hashCode  the hash code of the key to add
     * @param key  the key to add
     * @param value  the value to add
     */
    protected fun reuseEntry(
        entry: HashEntry<K,V>, hashIndex: Int, hashCode: Int,
        key: K, value: V,
    ) {
        entry.next = data[hashIndex]
        entry.hashCode = hashCode
        entry.key = key
        entry.value = value
    }


    /**
     * Gets the map as a String.
     *
     * @return a string version of the map
     */
    override fun toString(): String {
        if (isEmpty()) {
            return "{}"
        }
        val buf= StringBuilder(32 * size)
        buf.append('{')

        val it = mapIterator()
        var hasNext = it.hasNext()
        while (hasNext) {
            val key = it.next()
            val value = it.getValue()
            buf.append(if (key === this) "(this Map)" else key)
                .append('=')
                .append(if (value === this) "(this Map)" else value)

            hasNext = it.hasNext()
            if (hasNext) {
                buf.append(Char.COMMA).append(' ')
            }
        }

        buf.append('}')
        return buf.toString()
    }

    /**
     * Updates an existing key-value mapping to change the value.
     *
     *
     * This implementation calls `setValue()` on the entry.
     * Subclasses could override to handle changes to the map.
     *
     *
     * @param entry  the entry to update
     * @param newValue  the new value to store
     */
    fun updateEntry(entry: HashEntry<K,V>, newValue: V) {
        entry.setValue(newValue)
    }


    companion object {
        /** Exception message.  */
        protected const val NO_NEXT_ENTRY: String = "No next() entry in the iteration"

        /** Exception message.  */
        protected const val NO_PREVIOUS_ENTRY: String = "No previous() entry in the iteration"

        /** Exception message.  */
        protected const val REMOVE_INVALID: String = "remove() can only be called once after next()"

        /** Exception message.  */
        protected const val GETKEY_INVALID: String = "getKey() can only be called after next() and before remove()"

        /** Exception message.  */
        protected const val GETVALUE_INVALID: String = "getValue() can only be called after next() and before remove()"

        /** Exception message.  */
        protected const val SETVALUE_INVALID: String = "setValue() can only be called after next() and before remove()"

        /** The default capacity to use  */
        protected const val DEFAULT_CAPACITY: Int = 16

        /** The default threshold to use  */
        protected const val DEFAULT_THRESHOLD: Int = 12

        /** The default load factor to use  */
        protected const val DEFAULT_LOAD_FACTOR: Float = 0.75f

        /** The maximum capacity allowed  */
        protected val MAXIMUM_CAPACITY: Int = 1 shl 30

        /** An object for masking null  */
        protected val NULL: Any = Any()
    }
}
